package com.leetcode.dataStruct.tree;

import com.leetcode.dataStruct.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class RecoverTree {
    public static void main(String[] args) {

    }

    public void recoverTree(TreeNode root) {
        List<Integer> resList = new ArrayList<>();
        inorder(root, resList);
        int[] swaped = findTwoSwapped(resList);
        recover(2, root, swaped[0], swaped[1]);
    }

    private void inorder(TreeNode root, List<Integer> resList) {
        if (root == null) {
            return;
        }
        inorder(root.left, resList);
        resList.add(root.val);
        inorder(root.right, resList);
    }

    private int[] findTwoSwapped(List<Integer> nums) {
        int index1 = -1;
        int index2 = -1;
        int[] swaped = new int[2];
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums.get(i) > nums.get(i+1)) {
                index2 = i + 1;
                if (index1 == -1) {
                    index1 = i;
                } else {
                    break;
                }
            }
        }
        swaped[0] = nums.get(index1);
        swaped[1] = nums.get(index2);
        return swaped;
    }

    private void recover(int count, TreeNode root, int x, int y) {
        if (root != null) {
            if (root.val == x || root.val == y) {
                root.val = root.val == x ? y : x;
                if (--count == 0) {
                    return;
                }
            }
            recover(count, root.right, x, y);
            recover(count, root.left, x, y);
        }
    }
}
